package BinaryTree01;

import org.w3c.dom.Node;

import java.io.File;
import java.sql.PreparedStatement;
import java.sql.RowIdLifetime;
import java.util.*;
import java.util.concurrent.atomic.DoubleAdder;

public class BinaryTree {


    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char  val){
            this.val = val;
        }

    }

    private TreeNode root; //指向根节点

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

/*

    //二叉树的前序遍历操作:根->左->右
    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
*/


    //上强度(2.0版本,把前序遍历的结果存到一个list当中
    //二叉树的前序遍历操作:根->左->右

    public List<TreeNode> preOrder(TreeNode root){
        //新建一个ret变量,存储遍历的二叉树的结果,最后返回ret
        List<TreeNode> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }

        //先遍历根节点, 把根节点添加到ret中去
        ret.add(root);


        //之后用递归遍历左子树, 将遍历的结果存到临时变量leftTree中
        List<TreeNode>  leftTree = preOrder(root.left);

        //将leftTree的结果存到ret中去
        ret.addAll(leftTree);

        //最后进行右子树的遍历,将右子树遍历结果存到rightTree中
        List<TreeNode> rightTree = preOrder(root.right);


        //将rightTree的结果存到ret中去
        ret.addAll(rightTree);

        //最后我们返回将所有遍历结果存储好的ret
        return ret;



    }



    //二叉树的中序遍历 左->根->右
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //二叉树的后序遍历: 左->右->根
    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);

        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //使用前序遍历的方式来计算二叉树的总节点
    public int size = 0;
    public int sizeNode(TreeNode root){
        if(root == null){
            return 0;
        }

        //遍历根节点
        size++;

        //遍历左子树
        sizeNode(root.left);


        //遍历右子树
        sizeNode(root.right);
        return size;

    }



    //计算二叉树的左右子树和根节点来计算二叉树的总结点个数
    public int size02 = 0;
    public int sizeNode02(TreeNode root){

        if(root == null){
            return 0;
        }

        return 1 + sizeNode02(root.left) + sizeNode02(root.right);
    }


    //计算叶子结点的个数, 叶子结点是左子树为空并且右子树也为空的节点

    public int leafSize = 0;
    public int getLeafSize(TreeNode root){
        if(root == null){
            return 0;
        }

        if(root.left == null && root.right == null){
            leafSize++;
        }

        getLeafSize(root.left);
        getLeafSize(root.right);

        return leafSize;

    }

    //计算叶子结点的个数
    public int leafSize02 = 0;
    public int getLeafSize02(TreeNode root){

        if(root == null){
            return 0;
        }

        if(root.left == null && root.right == null){
            return 1;
        }


        return getLeafSize02(root.left) + getLeafSize02(root.right);

    }



    //获取第K层的节点的个数
    public int getKLevelCount(TreeNode root, int k){
        if(root == null){
            return 0;
        }

        if( k == 1){
            return 1;
        }

        return getKLevelCount(root.left, k -1) + getKLevelCount(root.right, k -1);

    }


    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);



    }







}
